The technique of employing a high speed cache memory intermediate a processor and a main memory to hold a dynamic subset of the information in the main memory in order to speed up system operation is well known in the art. Briefly, the cache holds a dynamically variable collection of main memory information fragments selected and updated such that there is a good chance that the fragments will include instructions and/or data required by the processor in upcoming operations. If there is a cache "hit" on a given operation, the information is available to the processor much faster than if main memory had to be accessed to obtain the same information. Consequently, in many high performance data processing systems, the "cache miss ratio" is one of the major limitations on the system execution rate, and it should therefore be kept as low as possible.
The key to obtaining a low cache miss ratio is obviously one of carefully selecting the information to be placed in the cache from main memory at any given instant. There are several techniques for selecting blocks of instructions for transitory residence in the cache, and the more or less linear use of instructions in programming renders these techniques statistically effective. However, the selection of operand information to be resident in cache memory at a given instant has been much less effective and has been generally limited to transferring one or more contiguous blocks including a cache miss address. This approach only slightly lowers the cache miss ratio and is also an ineffective use of cache capacity.
Thus, those skilled in the art will understand that it would be highly desirable to provide means for selecting operand information for transitory storage in a cache memory in such a manner as to significantly lower the cache miss ratio. That end was accomplished in accordance with the invention disclosed and claimed in U.S. patent application Ser. No. 07/364,943 filed Jun. 12, 1989, for METHOD AND APPARATUS FOR PREDICTING ADDRESS OF A SUBSEQUENT CACHE REQUEST UPON ANALYZING ADDRESS PATTERNS STORED IN SEPARATE MISS STACK by Charles P. Ryan, now U.S. Pat. No. 5,093,777, by special purpose apparatus in the cache memory which stores recent cache misses and searches for operand patterns therein. Any detected operand pattern is then employed to anticipate a succeeding cache miss by prefetching from main memory the block containing the predicted cache miss.
The cache miss prediction circuit disclosed therein was best adapted to operate in an environment where the main memory address space is linear and unbroken. However, in many processors, the main memory address space is paged with the sizes of the pages typically falling within the range 1024-4096 bytes. In a paged main memory environment, the memory address developed during normal operation is a virtual address that must be translated from the virtual configuration to a physical configuration. This is typically achieved by dividing the address into two fields. Some lower number of bits, which represent addressing within a page, are not translated. All the remaining, upper bits are translated by a paging unit within the processor from the virtual address space to a physical address space in a manner which is invisible to the running program. The principal purpose of providing a paged main memory is to permit addressing a much larger virtual memory; however, secondary purposes of importance include the facilitation of providing security to selected main memory pages and the ability to continue operation if a page of main memory is faulty.
The method and apparatus disclosed in U.S. Pat. No. 5,093,777 has the drawback that it is subject to making invalid predictions or a prediction that may cause a system problem when a page boundary in main memory is crossed since operation is with physical addresses. For example, a pattern which continues onto the next page of the physical main memory may enter memory space which is reserved to some other user (or even confidential) or process, or the next page may be damaged and not intended for use, or it may contain information which is of no value to have in the cache at the present time. If the prediction process carries across a page boundary into a reserved or damaged area of memory, the processor must handle the resulting invalid states before normal processing can continue, and such remedial action may impose a severe performance penalty. The present invention overcomes this inherent drawback of the prior art method and apparatus when used in a paged main memory system.